// 数组中只有1种数出现次数少于m次，其他数都出现了m次
// 返回出现次数小于m次的那种数
// 测试链接 : https://leetcode.cn/problems/single-number-ii/
// 注意 : 测试题目只是通用方法的一个特例，课上讲了更通用的情况
public class Code06_OneKindNumberLessMtimes {
    // singleNumber方法是针对特定m值（这里m = 3）的调用
    public static int singleNumber(int[] nums) {
        // 直接调用更通用的find方法，传入数组nums和m = 3
        return find(nums, 3);
    }

    // 更通用的方法
    // 已知数组中只有1种数出现次数少于m次，其他数都出现了m次
    // 返回出现次数小于m次的那种数
    public static int find(int[] arr, int m) {
        // 创建一个长度为32的整数数组cnts，用于统计数组arr中每个数的每一位上1的个数
        // cnts[0]用于统计0位上有多少个1
        // cnts[i]用于统计i位上有多少个1（0 <= i <= 31）
        // cnts[31]用于统计31位上有多少个1
        int[] cnts = new int[32];

        // 遍历数组arr中的每个数num
        for (int num : arr) {
            // 对于每个数num，遍历其每一位（从第0位到第31位）
            for (int i = 0; i < 32; i++) {
                // (num >> i) & 1用于获取num的第i位的值
                // 如果第i位为1，则(num >> i) & 1的结果为1，否则为0
                // 将获取到的值累加到cnts[i]中，从而统计出数组中所有数的第i位上1的总数
                cnts[i] += (num >> i) & 1;
            }
        }

        // 初始化结果变量ans为0
        int ans = 0;
        // 再次遍历cnts数组，检查每一位
        for (int i = 0; i < 32; i++) {
            // 如果cnts[i]除以m的余数不为0，说明出现次数小于m次的那个数在第i位上为1
            if (cnts[i] % m!= 0) {
                // 使用位运算将ans的第i位设置为1
                ans |= 1 << i;
            }
        }
        // 返回最终结果，即出现次数小于m次的那个数
        return ans;
    }
}